import java.util.*;

public class NDame extends Backtracking {
  int nrCarouri;

  public NDame(int numarCarouri) {
    nrCarouri=numarCarouri;
    ElemStiva elementGarda=new ElemStiva(null);
    stiva.add(elementGarda);
  }

  protected Object solutie() {
    if(stiva.size()<nrCarouri+1) return null;
    ArrayList solutie=new ArrayList();
    for(int j=1; j<stiva.size(); j++) {
      ElemStiva elementCurent=(ElemStiva)stiva.get(j);
      solutie.add(elementCurent.element);
    }
    return solutie;
  }

  protected Object succesor() {
    if(nrCarouri<=0) return null;
    if(stiva.isEmpty() || stiva.size()==(nrCarouri+1)) return null;
    int j;
    ElemStiva varfStiva=(ElemStiva)stiva.get(stiva.size()-1);
    if(varfStiva.ultimSuccesorVizitat==null) return new Integer(1);
    j=((Integer)varfStiva.ultimSuccesorVizitat).intValue();
    if(j>=nrCarouri) return null;
    return new Integer(j+1);
  }

  protected boolean esteValid(Object succesor) {
    boolean valid=true;
    int inaltimeStiva=stiva.size();
    int k=((Integer)succesor).intValue();
    int liniei, coloanai;
    for(liniei=1; liniei<inaltimeStiva && valid; liniei++) {
      coloanai=((Integer)((ElemStiva)stiva.get(liniei)).element).
          intValue();
      if(coloanai==k || Math.abs(k-coloanai)==
          (inaltimeStiva-liniei))  valid=false;
    }
    return valid;
  }
}
    